import java.util.HashMap;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code07_PreorderInorderBuildBinaryTree {

    // 不提交这个类
    // TreeNode类用于表示二叉树的节点
    // 其中val表示节点的值，left和right分别表示左子节点和右子节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 提交如下的方法
    public static TreeNode buildTree(int[] pre, int[] in) {
        // 如果先序遍历序列pre为null或者中序遍历序列in为null
        // 或者先序遍历序列和中序遍历序列的长度不相等
        // 则无法构建二叉树，直接返回null
        if (pre == null || in == null || pre.length!= in.length) {
            return null;
        }

        // 创建一个HashMap，用于存储中序遍历序列中每个节点值及其对应的索引
        HashMap<Integer, Integer> map = new HashMap<>();
        // 遍历中序遍历序列in，将每个节点值作为键，其索引作为值存入哈希表map中
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        // 调用f方法开始构建二叉树，传入先序遍历序列、先序遍历序列的起始索引0和结束索引pre.length - 1
        // 传入中序遍历序列、中序遍历序列的起始索引0和结束索引in.length - 1，以及构建好的哈希表map
        return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }

    public static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
        // 如果先序遍历序列中的当前子序列的起始索引l1大于结束索引r1
        // 表示当前子序列为空，没有节点可以构建子树，所以返回null
        if (l1 > r1) {
            return null;
        }

        // 根据先序遍历的性质，先序遍历序列中的第一个节点就是根节点
        // 创建一个值为pre[l1]的TreeNode作为根节点head
        TreeNode head = new TreeNode(pre[l1]);
        // 如果先序遍历序列中的当前子序列只有一个节点（即l1 == r1）
        // 表示这个节点就是叶子节点，直接返回该节点
        if (l1 == r1) {
            return head;
        }

        // 通过map.get(pre[l1])在中序遍历序列中找到根节点的值对应的索引k
        int k = map.get(pre[l1]);

        // 以下是根据中序遍历序列中左、右子树的划分来确定先序遍历序列中左、右子树的范围
        // pre : l1(........)[.......r1]
        // in  : (l2......)k[........r2]
        // (...)是左树对应，[...]是右树的对应

        // 对于左子树，在中序遍历中，其节点范围是l2到k - 1
        // 在先序遍历中，由于先序遍历的第一个节点是根节点，所以左子树的节点范围是从l1 + 1到l1 + k - l2
        // 递归调用f方法构建左子树，并将构建好的左子树赋值给head.left
        head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
        // 对于右子树，在中序遍历中，其节点范围是k + 1到r2
        // 在先序遍历中，右子树的节点范围是从l1 + k - l2 + 1到r1
        // 递归调用f方法构建右子树，并将构建好的右子树赋值给head.right
        head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);

        // 返回构建好的根节点head，完成整个二叉树的构建
        return head;
    }
}